View AN1338_717569.PDF datasheet online --- IC-ON-LINE

Datasheet File OCR Text:

AN1338 APPLICATION NOTE
Multiple Search Table Management Using the M7010 and M7020 Network Search Engines
INTRODUCTION This Application Note explains how multiple search tables having variable widths can be configured within the M7010 and M7020 Search Engines. Since the internal architecture of the M7010 and M7020 is similar, the following discussion on the table management applies to both Search Engine devices. The table management has been simplified in the M7040 Search Engine and it is explained later in this Application Note. M7010 and M7020 Using Associative Processing TechnologyTM (APT) The M7010 and M7020 are high-performance, pipelined, synchronous, Search Engines. The M7010 is organized as 8K x 136-bit, but can also be configured as 4K x 272-bit, 16K x 68-bit, or 32K x 34-bit (see Application Note "AN1339, 32-bit Applications Using the M7010, M7020 Network Search Engines"). The M7020 is organized as 16K x 136-bit, but can also be configured as 8K x 272-bit, 32K x 68-bit, or 64K x 34-bit (see Application Note "AN1339, 32-bit Applications Using the M7010, M7020 Network Search Engines"). The M7010 can sustain 83 million searches per second on any sub-field of a 68-bit or 136-bit field, making it the fastest Search Engine in the market. These high speed, high capacity chips can be employed in a variety of networking and communications applications that require fast searches of various tables. A unique feature of the M7010 and M7020 is their flexibility and ability to configure multiple search tables of different widths within the same device. By comparing the desired information against the entire list of pre-stored entries simultaneously, The M7010 and M7020 provide performance advantage over other memory search algorithms, such as binary or tree-based searches, thereby giving orders-of-magnitude reduction in the search time. Figure 1. Four 68-bit wide Quadrants in M7010
68
4K
AI04253
February 2001
1/8
AN1338 - APPLICATION NOTE
The M7010 consists of 16K x 68-bit storage cells referred to as data bits. There is a mask cell corresponding to each data cell. Three different configuration tables based on the value of the configuration bits [16:9] in the Command register of M7010 (see Figure 2). The M7020 consists of 32K x 68-bit storage cells. Figure 2. M7010 Structure
68 136 272
Data
Masks
16 K
8K Masks Data CFG = 01010101
4K
Masks Data CFG = 10101010
CFG = 00000000
AI04264
The M7010 is internally divided into four quadrants of 4K x 68-bits, each of which can be arranged as 4K x 68-bit, 2K x 136-bit, or 1K x 272-bits. It can be configured to contain tables of different widths within the same device. A typical configuration with tables of different widths is shown below (see Figure 3). Figure 3. Multi-width Configurations for the M7010
68 4K
68 4K
2K 1K
136 272 CFG = 10010000
AI04244
2/8
AN1338 - APPLICATION NOTE
There are eight configuration bits in the command register, which are bits [16:9]. They are subdivided into 2 bits for each quadrant (see Table 1). The supported table widths are shown in Table 2. Table 1. Configuration Bits for Each Quadrant
Quadrant Q1 Q2 Q3 Q4 Command bits 10:9 12:11 14:13 16:15
Table 2. Configuration Bits and Table Widths
Command Bit 00 01 10 CFG bits for each Quadrant 4K x 68-bit 2K x 136-bit 1K x 272-bits
Initially, these configuration bits have values of 00000000. Each quadrant may be set to one of the three configurations (see Figure 2 on page 2).
3/8
AN1338 - APPLICATION NOTE
Logical Tables with Variable Widths Using the M7010 and M7020 Search Engines The M7010 and M7020 Search Engines can be configured to contain more than one logical table within the device. To accomplish this, it is necessary to assign Table Identifier bits. It is possible to create multiple tables within the device with the help of these Table ID bits. Please note that when creating several tables, the total number of bits in all tables combined may not exceed 1Mbit for the M7010 and 2Mbits for the M7020. Figure 4 shows an example of maintaining six search tables, each of which having 68-bit width. In this case, the value of the configuration bits [16:9] is 00000000. Bits [3:1] are used as the Table Identifier bits. Bit 0 indicates whether the location is Full or Empty, as required by the Learn Mode. (See data sheets on the M7010 and M7020 for the description of Learn Mode). Figure 4. Six 68-bit Wide Tables in the M7010
x68 67 Table ID bits 0
5K
Source IP 32-bits
Destination IP 32-bits
000
1
Table 1
4K
Packet Filtering
001
1
Table 2
2K
Other Parameters
010
1
Table 3
2K
Other Parameters
011
1
Table 4
2K
Other Parameters
100
1
Table 5
1K
Other Parameters
101
1
Table 6
AI04248
4/8
AN1338 - APPLICATION NOTE
Search Tables with multiple widths using M7010/20 Search Engines Here is another example of how to create Search Tables with two different widths (see Figure 5). The device is configured to contain two search tables, one is 8K x 68-bit wide and the other is 4K x 136-bit wide. The configuration bits [16:9] in this case are 01010000. As in the previous example, Bits [2:1] are assigned as the Table Identifier bits. Bit 0 in is used to indicate if the entry is Full or Empty as required by the Learn Mode (see data sheets on the M7010 and M7020 for description of Learn Mode). For 136-bit wide table, it is necessary to enter the table ID bits [2:1] in both 68-bit wide quadrants, because the search starts in both 68-bit quadrants simultaneously. Even though the search in intended in the 136-bit wide table, it is possible to find an erroneous match in the 68-bit quadrant, if the Table ID bits are not used in each 68-bit quadrant. Figure 5. 68-bit and 136-bit Wide Tables for the M7010
68
8K
00 1
4K
10 1
10 1
136 bits
AI04249
5/8
AN1338 - APPLICATION NOTE
Figure 6 shows an example of creating three tables with different widths. The configuration bits [16:9] in this example are 10010000. Bits [1:0] are assigned as the Table Identifier bits. In this example, the Learn mode is not used. Therefore, Bit 0 can be used as a Table ID bit. As in the previous example, it is necessary to enter the Table ID bits in each of the 68-bit quadrants. Without doing this, an erroneous match can be found in any of the 68-bit wide table. Figure 6. Table Configuration with Different Widths for the M7010
68
8K
00
136 2K 01 01 272 1K 10 10 10 10
AI04247
6/8
AN1338 - APPLICATION NOTE
The STMicroelectronics M7010 and M7020 Search Engines offer the unique feature of allowing the creation of search tables of variable widths within the same device. This approach offers a cost-effective solution for small size applications. Another versatile feature is the depth cascading of several Search Engines. Depth cascading of up to eight devices will enable the formation of table sizes of 128K x 68-bit, 64K x 136-bits or 32K x 272 bits. Depth cascading can be further expanded by cascading up to 31 devices, whereby the table sizes can be expanded to 496 x 68-bit, 248K x 136 bits 124K x 272 bits. These numbers are for the M7010. When using the M7020, the depth of the memory doubles. With the proliferation of the Internet related services such as VPN, QoS, and CoS, the demand on very large searches and look-ups is increasing. Consequently, the software search tables, which are slower and may become expensive with increasing search table sizes, cannot meet these requests. Using ST Microelectronics Search Engine modules can further expand the table sizes when they are cascaded.
CONTACT INFORMATION If you have any questions or suggestions concerning the matters raised in this document, please send them to the following electronic mail addresses:
apps.nvram@st.com ask.memory@st.com
(for application support) (for general inquiries)
Please remember to include your name, company, location, telephone number, and fax number.
7/8
AN1338 - APPLICATION NOTE
Information furnished is believed to be accurate and reliable. However, STMicroelectronics assumes no responsibility for the consequences of use of such information nor for any infringement of patents or other rights of third parties which may result from its use. No license is granted by implication or otherwise under any patent or patent rights of STMicroelectronics. Specifications mentioned in this publication are subject to change without notice. This publication supersedes and replaces all information previously supplied. STMicroelectronics products are not authorized for use as critical components in life support devices or systems without express written approval of STMicroelectronics. The ST logo is registered trademark of STMicroelectronics All other names are the property of their respective owners. (c) 2001 STMicroelectronics - All Rights Reserved STMicroelectronics GROUP OF COMPANIES Australia - Brazil - China - Finland - France - Germany - Hong Kong - India - Italy - Japan - Malaysia - Malta - Morocco Singapore - Spain - Sweden - Switzerland - United Kingdom - U.S.A. www.st.com
8/8

▲Up To Search▲

Price & Availability of AN1338

	To Download AN1338 Datasheet File
If you can't view the Datasheet, Please click here to try to view without PDF Reader .